The invention relates to methods for updating a Linear Feedback Shift Register of a code generator, and to code generators using the methods. The term xe2x80x98codexe2x80x99 refers to, for example, a pseudo-noise sequence used in a radio system, such as a spreading code or scrambling code of a radio system employing code division multiple access (CDMA), or another code (used for example in an encryption system).
In radio systems employing code division multiple access radio resources are divided between a plural number of different users on a code-division basis. The payload of each user is spread on a wide frequency band (of five megaherz, for example) by multiplying the payload by a spreading code. The receiver can separate the signal it wants to receive by multiplying the received signal by the spreading code used. Portions of the spreading code are called chips, and in fact they are bits. A chip value can be expressed with zeros and ones, or as real numbers with ones and minus ones. Chip rate is typically significantly faster, over hundred times, for example, than payload rate.
In addition to spreading codes, codes known as scrambling codes can be used. They are not necessarily used for spreading the signal any more, but for scrambling the bits of the spread signal by multiplying each bit in the signal by the corresponding scrambling code bit. Scrambling codes can be extremely long, 241xe2x88x921 chips, for example.
The spreading codes used are normally as orthogonal as possible with respect to each other. Spreading codes can be obtained for example from a Hadamard matrix. A Hadamard matrix Mn is an nxc3x97n matrix (where n is an even integer) composed of zeros and ones in such a way that any matrix line differs from any other matrix line exactly at an n/2 position. Consequently, one matrix line comprises only zeros, whereas the rest of the lines are composed of an equal number of zeros and ones. When n=2, the following Hadamard matrix is obtained:                               M          2                =                  [                                                    0                                            0                                                                    0                                            1                                              ]                                    (        1        )            
A Hadamard matrix M2n is generated from the Hadamard matrix Mn by the following relation:                               M                      2            ⁢            n                          =                  [                                                                      M                  n                                                                              M                  n                                                                                                      M                  n                                                                                                  M                    _                                    n                                                              ]                                    (        2        )            
where the matrix {overscore (M)}n is a complement of the matrix Mn, i.e. the zeros are replaced by ones and ones by zeros. The matrix 1 thus provides the following:                               M          4                =                  [                                                    0                                            0                                            0                                            0                                                                    0                                            1                                            0                                            1                                                                    0                                            0                                            1                                            1                                                                    0                                            1                                            1                                            0                                              ]                                    (        3        )            
Further, the matrix 3 provides the following:                               M          8                =                  [                                                    0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                                                    0                                            1                                            0                                            1                                            0                                            1                                            0                                            1                                                                    0                                            0                                            1                                            1                                            0                                            0                                            1                                            1                                                                    0                                            1                                            1                                            0                                            0                                            1                                            1                                            0                                                                    0                                            0                                            0                                            0                                            1                                            1                                            1                                            1                                                                    0                                            1                                            0                                            1                                            1                                            0                                            1                                            0                                                                    0                                            0                                            1                                            1                                            1                                            1                                            0                                            0                                                                    0                                            1                                            1                                            0                                            1                                            0                                            0                                            1                                              ]                                    (        4        )            
If elements of the above described Hadamard matrices, i.e. zeros and ones, are represented by ones and minus ones, then the lines in the Hadamard matrices are orthogonal with respect to each other. If desired, the values could also be inverted, i.e. zeros could be replaced by ones and ones by zeros, but that would not change the properties of the matrix. Hence, the matrix 1 could also be presented in formats such as             M      2        ⁡          [                                    1                                1                                                1                                0                              ]        ,      xe2x80x83    ⁢            M      2        =          [                                    1                                1                                                1                                              -              1                                          ]      
Each matrix line forms one spreading code. The length of the spreading code varies according to the desired spreading factor. The spreading codes can be numbered for example by indicating the code class of the spreading code and its ordinal number in the code class concerned. The code class can be obtained by the following equation: two to the power of code class equals the length of the spreading code, in other words, the code class is a binary logarithm of the spreading code. The matrix 4, for example, thus includes the following spreading codes (the subindex denotes the code class and the number in parenthesis is the ordinal number):
SPREADINGCODE3(0)={0,0,0,0,0,0,0,0}
SPREADINGCODE3(1)={0,1,0,1,0,1,0,1}
SPREADINGCODE3(2)={0,0,1,1,0,0,1,1}
SPREADINGCODE3(3)={0,1,1,0,0,1,1,0}
SPREADINGCODE3(4)={0,0,0,0,1,1,1,1}
SPREADINGCODE3(5)={0,1,0,1,1,0,1,0}
SPREADINGCODE3(6)={0,0,1,1,1,1,0,0}
SPREADINGCODE3(7)={0,1,1,0,1,0,0,1}
According to prior art, all short spreading codes are stored into a transceiver memory. For a code of a class 8, for example, this means that 256 different codes of 256 chips are stored into the memory, the memory space needed being 256xc3x97256 bits, i.e. a total of 65536 bits. Shorter spreading codes can be generated from the stored long codes, therefore spreading codes of lower code classes need not be separately stored.
Spreading codes can be remarkably long, 241xe2x88x921 chips for example. A technical problem that arises is how to generate the code in real time, because one and the same sequence is typically used, only different transceivers use the sequence at different stages. Ideally, the code sequence to be generated would be fully random; this is, however, not practical because both the transmitter and the receiver have to be able to generate the code sequence to be used, applying even the same timing, i.e. phase.
The code is generated by means of a code generator, for example a generator using a linear feedback shift register. WO Publication 96/36137 describes a linear feedback shift register that is used for generating what is known as an m sequence (maximal length sequence) to provide a pseudo noise sequence to be used as a code, the sequence being iterated after a sequence of 2Nxe2x88x921, where N represents the number of elements in the linear feedback shift register. The initial state is always known in linear feedback shift registers, but a problem arises from how to shift from the known initial state to a new, unknown target state which is at a known offset. In the solution described in the above publication a conversion matrix corresponding to each shift, or at least to each shift corresponding to a power of two, is stored, the conversion matrix indicating how each initial state element needs to be converted to provide target state elements. Consequently, the amount of bits stored for a spreading code of 241xe2x88x921 chips, for example, is 41xc3x9741xc3x9741 bits (the number of different powers of two xc3x97 the number of linear feedback shift register elements xc3x97 the length of the linear feedback shift register), i.e. 68921 bits in total.
U.S. Pat. No. 5,835,528 discloses how a feedback shift register is updated from a known current state to a new state which is at a known offset. The solution involves storing pre-calculated states that are used for updating. The solution requires memory for storing the states calculated in advance, and only states that are at an offset determined by these states can be updated.
An object of the invention is to provide a method for updating a linear feedback shift register, wherein the method employs memory only a little and provides efficient calculation. This is achieved with a method for updating a Galois-type linear feedback shift register of a code generator to a target state which is at a known offset from a unit state. The method comprises the following: generating a binary offset number illustrating the offset; generating a counter showing the number of bits in the binary offset number; initializing a temporary state with the unit state; iterating as long as the counter value is higher than zero: applying a Galois Field multiplication to multiply the temporary state by itself; shifting the temporary state one state forward from the current temporary state if the value of a binary offset number bit shown by the counter is one; and decrementing the counter value by one; in the end, when the counter has reached the value zero, setting the temporary state as the target state.
The invention also relates to a method for updating a Galois-type linear feedback shift register of a code generator to a new state which is at a known offset from a known current state. The method comprises the following: generating a binary offset number illustrating the offset; generating a counter showing the number of bits in the binary offset number; initializing a temporary state with a unit state; iterating as long as the counter value is higher than zero: applying a Galois Field multiplication to multiply the temporary state by itself; shifting the temporary state one state forward from the current temporary state if the value of a binary offset number bit shown by the counter is one; and decrementing the counter value by one; in the end, when the counter has reached the value zero, performing a Galois Field multiplication between the temporary state and the current state; and setting the state obtained as a result of the multiplication as the new state.
The invention further relates to a method for updating a Fibonacci-type linear feedback shift register of a code generator to a new state which is at a known offset from a known current state. The method comprises the following: generating a binary offset number illustrating the offset; generating a counter showing the number of bits in the binary offset number; initializing a Galois-type temporary state with a unit state; iterating as long as the counter value is higher than zero: applying a Galois Field multiplication to multiply the temporary state by itself; shifting the temporary state one state forward from the current temporary state if the value of a binary offset number bit shown by the counter is one; and decrementing the counter value by one; in the end, when the counter has reached the value zero, performing a Galois Field multiplication between the Galois-type temporary state and the Fibonacci-type current state; and setting the state obtained as a result of the multiplication as the new state of the Fibonacci-type.
The invention still further relates to a code generator in a radio system, the code generator comprising the following: means for generating a binary offset number illustrating a known offset from a unit state of a Galois-type linear feedback shift register to a target state; means for generating a counter showing the number of bits in the binary offset number; means for initializing a temporary state with the unit state; means for iterating the operation of subsequent means as long as the counter value is higher than zero: means for applying a Galois Field multiplication to multiply the temporary state by itself; means for shifting the temporary state one state forward from the current temporary state, if the value of the binary offset number bit shown by the counter is one; and means for decrementing the counter value by one; means for setting, in the end, the temporary state as the target state when the counter has reached the value zero.
The invention also relates to a code generator in a radio system, the code generator comprising the following: means for generating a binary offset number illustrating a known offset from a known current state of a Galois-type linear feedback shift register of a code generator to a new state; means for generating a counter showing the number of bits in the binary offset number; means for initializing a temporary state with a unit state; means for iterating the operation of subsequent means as long as the counter value is higher than zero: means for applying a Galois Field multiplication to multiply the temporary state by itself; means for shifting the temporary state one state forward from the current temporary state if the value of the binary offset number bit shown by the counter is one; and means for decrementing the counter value by one; means for multiplying the temporary state and the current state by applying the Galois Field multiplication, and for setting the state obtained as a result of the multiplication as the new state when the counter has reached the value zero.
The invention still further relates to a code generator in a radio system, the code generator comprising the following: means for generating a binary offset number illustrating a known offset from a known current state of a Fibonacci-type linear feedback shift register to a new state; means for generating a counter showing the number of bits in the binary offset number; means for initializing a Galois-type temporary state with a unit state; means for iterating the operation of subsequent means as long as the counter value is higher than zero: means for applying a Galois Field multiplication to multiply the temporary state by itself; means for shifting the temporary state one state forward from the current temporary state, if the value of the binary offset number bit shown by the counter is one; and means for decrementing the counter value by one; means for multiplying the Galois-type temporary state and the Fibonacci-type current state by applying the Galois Field multiplication, and for setting the state obtained as a result of the multiplication as the new state of the Fibonacci-type when the counter has reached the value zero.
The dependent claims relate to the preferred embodiments of the invention.
The invention is based on applying Galois Field mathematical properties to provide efficient calculation for the processing of feedback shift registers, and on taking into account the connections between different types of feedback shift registers.